// 紧凑的对称布局
let nodeList = [
    { id: 1 },
    { id: 2 },
    { id: 3 },
    { id: 4 },
    { id: 5 },
    { id: 6 },
    { id: 7 },
    { id: 8 },
    { id: 9 },
    { id: 10 },
    { id: 11 },
    { id: 12 },
    { id: 13 }
];

let linkList = [
    { source: 1, target: 2 },
    { source: 1, target: 8 },
    { source: 2, target: 3 },
    { source: 3, target: 4 },
    { source: 3, target: 5 },
    { source: 3, target: 6 },
    { source: 4, target: 7 },
    { source: 5, target: 7 },
    { source: 6, target: 7 },
    { source: 8, target: 9 },
    { source: 8, target: 12 },
    { source: 9, target: 10 },
    { source: 12, target: 13 },
    { source: 10, target: 11 },
    { source: 13, target: 11 }
];

let linkMap = {};
for (let i = 0; i < linkList.length; i++) {
    const source = linkList[i].source;
    const target = linkList[i].target;
    if (linkMap[source]) {
        linkMap[source].push(target);
    } else {
        linkMap[source] = [target];
    }
    if (linkMap[target]) {
        linkMap[target].push(source);
    } else {
        linkMap[target] = [source];
    }
}

let rootId = 1;
let tree = { id: 1, children: [], level: 0 };
let sameLevelNodeListMap = {
    0: [tree]
};
let queue = [tree];
let visited = new Set([tree.id]);

// 构建树和层级树
while (queue.length > 0) {
    let queueHead = queue.shift();
    let queueHeadId = queueHead.id;
    let adjIdList = linkMap[queueHeadId];
    for (let i = 0; i < adjIdList.length; i++) {
        const adjId = adjIdList[i];
        if (!visited.has(adjId)) {
            visited.add(adjId);
            let tempChild = {
                id: adjId,
                children: [],
                level: queueHead.level + 1
            };
            queueHead.children.push(tempChild);
            queue.push(tempChild);
            if (!sameLevelNodeListMap[queueHead.level + 1]) {
                sameLevelNodeListMap[queueHead.level + 1] = [tempChild];
            } else {
                sameLevelNodeListMap[queueHead.level + 1].push(tempChild);
            }
        }
    }
}

console.log(tree);
console.log(sameLevelNodeListMap);

// 层序遍历逐步扩展空间
tree.x = 0;
tree.y = 0;
queue = [tree];
let lastLevel = 0;
let lastY = 0;
// debugger
while (queue.length > 0) {
    let queueHead = queue.shift();
    let children = queueHead.children;

    if (children.length > 1) {
        let ySpace = children.length - 1;
        // 1. 如果是第1个
        if (children[0].level > lastLevel) {
            lastLevel = children[0].level;
            lastY = moveChildPostion(queueHead, queue, ySpace, lastY);
            // let yStart = queueHead.y + ySpace / 2;
            // for (let i = 0; i < children.length; i++) {
            //     let child = children[i];
            //     queue.push(child);
            //     lastY = yStart - i;
            //     child.x = child.level;
            //     child.y = yStart - i;
            // }
            continue;
        }

        // 2. 如果不是第1个， 如果和父亲的Y中心位置重合
        let tryPositinMidY = lastY - 1 - ySpace / 2;
        if (tryPositinMidY === queueHead.y) {
            lastY = moveChildPostion(queueHead, queue, ySpace, lastY);
            // let yStart = queueHead.y + ySpace / 2;
            // for (let i = 0; i < children.length; i++) {
            //     let child = children[i];
            //     queue.push(child);
            //     lastY = yStart - i;
            //     child.x = child.level;
            //     child.y = yStart - i;
            // }
            continue;
        }

        // 3. 如果不是第1个， 如果比父亲的Y中心位置偏上处理, 所有直接祖先节点平移
        if (tryPositinMidY < queueHead.y) {
            let moveTopY = queueHead.y - tryPositinMidY;
            moveAncestorsTopY(queueHead, moveTopY);
            lastY = moveChildPostion(queueHead, queue, ySpace, lastY);
        }
        // 4. 如果不是第1个， 如果比父亲的Y中心位置偏下不处理
    } else {
        if (children.length === 0) {
            continue;
        }
        let onlyChild = children[0];
        // 找到所有父节点的中心Y坐标
        let parentLevelNodeList = sameLevelNodeListMap[queueHead.level];
        let sumY = 0;
        let parentNodeNum = 0;
        for(let i=0; i<parentLevelNodeList.length; i++) {
            if (!onlyChild || !parentLevelNodeList[i]) {
                debugger
            }
            if (linkMap[onlyChild.id].includes(parentLevelNodeList[i].id)) {
                sumY += parentLevelNodeList[i].y;
                parentNodeNum++;
            }
        }
        let tryPositinMidY = sumY / parentNodeNum;
        // 1. 如果是第1个
        if (onlyChild.level > lastLevel) {
            lastLevel = onlyChild.level;
            onlyChild.x = onlyChild.level;
            onlyChild.y = tryPositinMidY;
            lastY = tryPositinMidY;
            queue.push(onlyChild);
            // let yStart = queueHead.y + ySpace / 2;
            // for (let i = 0; i < children.length; i++) {
            //     let child = children[i];
            //     queue.push(child);
            //     lastY = yStart - i;
            //     child.x = child.level;
            //     child.y = yStart - i;
            // }
            continue;
        }

        // 2. 如果不是第1个， 如果和父亲的Y中心位置重合
        if (tryPositinMidY === queueHead.y) {
        // if (tryPositinMidY === lastY - 1) {
            lastY = moveChildPostion(queueHead, queue, 0, lastY);
            // let yStart = queueHead.y + ySpace / 2;
            // for (let i = 0; i < children.length; i++) {
            //     let child = children[i];
            //     queue.push(child);
            //     lastY = yStart - i;
            //     child.x = child.level;
            //     child.y = yStart - i;
            // }
            continue;
        }

        // 3. 如果不是第1个， 如果比父亲的Y中心位置偏上处理, 所有直接祖先节点平移
        if (tryPositinMidY < queueHead.y) {
        // if (tryPositinMidY < lastY - 1) {
            let moveTopY = lastY - tryPositinMidY;
            moveAncestorsTopY(queueHead, moveTopY);
            lastY = moveChildPostion(queueHead, queue, 0, lastY);
        }
        // 4. 如果不是第1个， 如果比父亲的Y中心位置偏下不处理
    }
}

console.log(sameLevelNodeListMap);

for (const level in sameLevelNodeListMap) {
    if (Object.prototype.hasOwnProperty.call(sameLevelNodeListMap, level)) {
        sameLevelNodeListMap[level].forEach(element => {
            document.getElementById(`item_${element.id}`).style.left = element.x * 100 + 500 + 'px'
            document.getElementById(`item_${element.id}`).style.top = element.y * 100 + 500 + 'px'

        })
    }
}

function moveChildPostion(parentNode, queue, ySpace, lastY) {
    let children = parentNode.children;
    if (children.length === 0) {
        return lastY; 
    }
    
    let yStart = parentNode.y + ySpace / 2;
    let tempLastY;
    for (let i = 0; i < children.length; i++) {
        let child = children[i];
        queue.push(child);
        tempLastY = yStart - i;
        child.x = child.level;
        child.y = yStart - i;
    }
    return tempLastY;
}
// 移动当前节点和当前节点之后的节点， 还有他们的祖先节点
function moveAncestorsTopY(treeNode, moveTopY) {
    // treeNode.y -= moveTopY;
    // 移动同层之后的节点
    let siblingLevelNodeList = sameLevelNodeListMap[treeNode.level];
    let childNodeList = [];
    for (let i = siblingLevelNodeList.length - 1; i >= 0; i--) {
        siblingLevelNodeList[i].y -= moveTopY;
        childNodeList.push(siblingLevelNodeList[i]);
        if (siblingLevelNodeList[i].id === treeNode.id) {
            break;
        }
    }

    while (childNodeList.length > 0) {
        let parentLevelNodeList = sameLevelNodeListMap[childNodeList[0].level - 1] || [];
        let preChildNodeList = childNodeList;
        childNodeList = [];
        for (let i = parentLevelNodeList.length - 1; i >= 0; i--) {
            let isFindChild = false;
            let childIdSet = new Set(
                parentLevelNodeList[i].children.map(item => item.id)
            );
            for (let j = 0; j < preChildNodeList.length; j++) {
                if (childIdSet.has(preChildNodeList[j].id)) {
                    isFindChild = true;
                    break;
                }
            }
            if (!isFindChild) {
                break;
            }
            parentLevelNodeList[i].y -= moveTopY;
            childNodeList.push(parentLevelNodeList[i]);
        }
    }
}
